package com.lwx.leetcode.offer.easy;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Offer39 {
    public static void main(String[] args) {
        Offer39 o = new Offer39();
        int[] nums = {1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(o.majorityElement(nums));
    }
    public int majorityElement(int[] nums) {
        if(nums ==null){
            return 0;
        }
        HashMap<Integer,Integer> retMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(retMap.get(nums[i]) == null){
                retMap.put(nums[i],1);
            }else {
                Integer num = retMap.get(nums[i]);
                if(num > nums.length/2){
                    return nums[i];
                }else {
                    retMap.put(nums[i], num+1);
                }
            }
        }
        Iterator<Map.Entry<Integer, Integer>> iterator = retMap.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry<Integer, Integer> map = iterator.next();
            Integer num = map.getValue();
            if(num > nums.length/2){
                return map.getKey();
            }
        }

        return 0;

    }

}
